package leetcode;

/**
 * Created by Ghost on 2014/12/20.
 */
public class Unique_Paths_II {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] w = new int[m][n];
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1){
                for(;i<m;i++)
                    w[i][0] = 0;
            }
            else
                w[i][0]=1;
        }
        for(int i=0;i<n;i++){
            if(obstacleGrid[0][i]==1){
                for(;i<n;i++)
                    w[0][i] = 0;
            }
            else
                w[0][i]=1;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1)
                    w[i][j]=0;
                else
                    w[i][j] = w[i-1][j]+w[i][j-1];
            }
        }
        return w[m-1][n-1];
    }

    public static void main(String[] args){
        Unique_Paths_II unique_paths_ii = new Unique_Paths_II();
        int[][] N = {{1,0}};
        System.out.println(unique_paths_ii.uniquePathsWithObstacles(N));
    }
}
